package nu.aing.P20140519;

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;

/**
 * MENTOK !!! MO NYONTEK DULU !!!
 * 
 * @author memekmaut@gmail.com
 */
public class DropCoins {
    
    static final String[] EX0 = new String[] {
        ".o..",
        "oooo",
        "..o."
    };
    static final String[] EX1 = new String[] {
        ".....o",
        "......",
        "oooooo",
        "oooooo",
        "......",
        "o....."
    };
    static final String[] EX2 = new String[] {
        "....",
        ".oo.",
        ".oo.",
        "...."
    };
    static final String[] EX3 = new String[] {
        ".......",
        "..ooo..",
        "ooooooo",
        ".oo.oo.",
        "oo...oo"
    };
    static final String[] EX4 = new String[] {
        ".................",
        ".ooooooo...oooo..",
        ".ooooooo..oooooo.",
        ".oo.......oo..oo.",
        ".oo.......oo..oo.",
        ".ooooo.....oooo..",
        ".ooooooo...oooo..",
        ".....ooo..oo..oo.",
        "......oo..oo..oo.",
        ".ooooooo..oooooo.",
        ".oooooo....oooo..",
        "................."
    };
    
    public static void main(String[] args) {
        System.out.println(getMinimum(EX0, 3) );
        System.out.println(getMinimum(EX1, 12) );
        System.out.println(getMinimum(EX2, 3) );
        System.out.println(getMinimum(EX3, 12) );
        System.out.println(getMinimum(EX4, 58) );
    }
    
    public static int getMinimum(String[] board, final int K) {
        int limit = 100;
        
        String[] boardHolder = Arrays.copyOf(board, board.length);
        int prevCircles = checkRemainingCircle(board);
        int trying = 0;
        
        while(limit > 0) {
            if(boardHolder.length == 0 || prevCircles < K) {
                boardHolder = Arrays.copyOf(board, board.length);
                continue;
            }
            
            trying++;
            
            String[] up = moveUp(boardHolder);
            String[] down = moveDown(boardHolder);
            String[] right = moveRight(boardHolder);
            String[] left = moveLeft(boardHolder);
            
            int upCircle = checkRemainingCircle(up);
            int downCircle = checkRemainingCircle(down);
            int rightCircle = checkRemainingCircle(right);
            int LeftCircle = checkRemainingCircle(left);
            
            int KminUp = K - upCircle;
            int KminDown = K - downCircle;
            int KminRight = K - rightCircle;
            int KminLeft = K - LeftCircle;
            
            List<Pair> smaller = new LinkedList<Pair>();
            
            if(upCircle > K) {
                smaller.add(new Pair(up, upCircle, KminUp) );
            }
            else if(upCircle == K) {
                return trying;
            }
            
            if(downCircle > K) {
                smaller.add(new Pair(down, downCircle, KminDown) );
            }
            else if(downCircle == K) {
                return trying;
            }
            
            if(rightCircle > K) {
                smaller.add(new Pair(right, rightCircle, KminRight) );
            }
            else if(rightCircle == K) {
                return trying;
            }
            
            if(LeftCircle > K) {
                smaller.add(new Pair(left, LeftCircle, KminLeft) );
            }
            else if(LeftCircle == K) {
                return trying;
            }
            
            if(smaller.isEmpty() ) {
                boardHolder = Arrays.copyOf(board, board.length);
                continue;
            }
            
            Collections.sort(smaller, new Comparator<Pair>() {
                @Override
                public int compare(Pair o1, Pair o2) {
                    if(o1.kMin < o2.kMin) {
                        return 1;
                    }
                    else if(o1.kMin > o2.kMin) {
                        return -1;
                    }
                    return 0;
                }
            });
            
            prevCircles = smaller.get(0).circle;
            boardHolder = smaller.get(0).array;
            
            limit--;
        }
        
        return -1;
    }
    
    private static int checkRemainingCircle(String[] board) {
        int remainingCircle = 0;
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[i].length(); j++) {
                if(board[i].charAt(j) == 'o') {
                    remainingCircle++;
                }
            }
        }
        return remainingCircle;
    }
    
    private static String[] moveUp(String[] board) {
        String[] temp = new String[board.length - 1];
        for(int i = 0; i < board.length -1; i++) {
            temp[i] = board[i+1];
        }
        
        return temp;
    }
    
    private static String[] moveDown(String[] board) {
        String[] temp = new String[board.length - 1];
        for(int i = 0; i < board.length - 1; i++) {
            temp[i] = board[i];
        }
        
        return temp;
    }
    
    private static String[] moveLeft(String[] board) {
        String[] temp = new String[board.length];
        for(int i = 0; i < board.length; i++) {
            temp[i] = board[i].substring(1, board[i].length() );
        }
        
        return temp;
    }
    
    private static String[] moveRight(String[] board) {
        String[] temp = new String[board.length];
        for(int i = 0; i < board.length; i++) {
            temp[i] = board[i].substring(0, board[i].length() - 1);
        }
        
        return temp;
    }

    private static final class Pair {
        String[] array;
        int circle;
        int kMin;
        
        public Pair(String[] array, int circle, int kMin) {
            this.array = array;
            this.circle = circle;
            this.kMin = kMin;
        }
        
        @Override
        public String toString() {
            return "["+circle+"]["+kMin+"]";
        }
    }
    
}
